class Solution:
    def validateStackSequences(self, pushed, popped) -> bool:
        stack = []
        k = 0
        for i in pushed:
            stack.append(i)
            while stack and stack[-1] == popped[k]:
                stack.pop()
                k += 1
        return not stack

if __name__ == '__main__':
    c = Solution()
    c.validateStackSequences([1,2,3,4,5],[4,5,3,2,1])